#pragma once
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <optional>
#include <cmath>
#include "grid.h"

struct AlgoState {
    std::set<long long> frontier;
    std::set<long long> visited;
    std::vector<Pos> path;
    bool finished;
    bool found;
};

inline long long key(Pos p, int cols) { return (long long)p.r * cols + p.c; }

class Algorithm {
public:
    virtual ~Algorithm() = default;
    virtual void reset(const Grid& g) = 0;
    virtual void step(const Grid& g) = 0;
    virtual AlgoState state() const = 0;
};

class BFS : public Algorithm {
    std::queue<Pos> q;
    std::map<long long, long long> parent;
    std::set<long long> visited;
    std::set<long long> frontier_s;
    std::vector<Pos> path_cache;
    bool fin;
    bool found;
public:
    void reset(const Grid& g) override;
    void step(const Grid& g) override;
    AlgoState state() const override;
};

class DFS : public Algorithm {
    std::stack<Pos> st;
    std::map<long long, long long> parent;
    std::set<long long> visited;
    std::set<long long> frontier_s;
    std::vector<Pos> path_cache;
    bool fin;
    bool found;
public:
    void reset(const Grid& g) override;
    void step(const Grid& g) override;
    AlgoState state() const override;
};

class Dijkstra : public Algorithm {
    struct Node { Pos p; int g; };
    struct Cmp { bool operator()(const Node& a, const Node& b) const { return a.g > b.g; } };
    std::priority_queue<Node, std::vector<Node>, Cmp> pq;
    std::map<long long, long long> parent;
    std::map<long long, int> dist;
    std::set<long long> visited;
    std::set<long long> frontier_s;
    std::vector<Pos> path_cache;
    bool fin;
    bool found;
public:
    void reset(const Grid& g) override;
    void step(const Grid& g) override;
    AlgoState state() const override;
};

class AStar : public Algorithm {
    struct Node { Pos p; int g; int f; };
    struct Cmp { bool operator()(const Node& a, const Node& b) const { return a.f > b.f; } };
    std::priority_queue<Node, std::vector<Node>, Cmp> pq;
    std::map<long long, long long> parent;
    std::map<long long, int> dist;
    std::set<long long> visited;
    std::set<long long> frontier_s;
    std::vector<Pos> path_cache;
    bool fin;
    bool found;
public:
    void reset(const Grid& g) override;
    void step(const Grid& g) override;
    AlgoState state() const override;
};

class GBFS : public Algorithm {
    struct Node { Pos p; int h; };
    struct Cmp { bool operator()(const Node& a, const Node& b) const { return a.h > b.h; } };
    std::priority_queue<Node, std::vector<Node>, Cmp> pq;
    std::map<long long, long long> parent;
    std::set<long long> visited;
    std::set<long long> frontier_s;
    std::vector<Pos> path_cache;
    bool fin;
    bool found;
public:
    void reset(const Grid& g) override;
    void step(const Grid& g) override;
    AlgoState state() const override;
};

class BiBFS : public Algorithm {
    std::queue<Pos> qa, qb;
    std::map<long long, long long> pa, pb;
    std::set<long long> va, vb;
    std::set<long long> frontier_s;
    std::vector<Pos> path_cache;
    bool fin;
    bool found;
    std::optional<Pos> meet;
public:
    void reset(const Grid& g) override;
    void step(const Grid& g) override;
    AlgoState state() const override;
};

int heuristic(const Grid& g, Pos a, Pos b);
std::vector<Pos> rebuild_path(const Grid& g, const std::map<long long,long long>& parent, Pos end);
std::vector<Pos> rebuild_bi_path(const Grid& g, const std::map<long long,long long>& pa, const std::map<long long,long long>& pb, Pos meet);
